package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a11_加油站复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/14
 */
public class a11_加油站复习3 {
    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
    }
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = gas[i] - cost[i];
        }

        int total = Arrays.stream(diff).sum();
        if(total < 0){
            return -1;
        }

        int sum = 0;
        int idx = 0;
        boolean[] used = new boolean[gas.length];
        while (true){
            if(used[idx]){
                return idx;
            }

            sum += diff[idx];
            used[idx] = true;
            if(sum < 0){
                sum = 0;
                Arrays.fill(used, false);
            }
            if(idx == gas.length - 1){
                idx = 0;
            }else {
                idx++;
            }
        }
    }
}
